#include <stdio.h>
#include <stdlib.h>

/*
	代码实现散列查找，散列函数使用除留余数法，
	冲突处理方法使用开放地址法中的二次探测再散列。
*/

int hash(int key, int n)
{
	return key % n;
}

int sum(int array[], int n)
{
	int total = 0;
	int i;
	for (i = 0; i < n; i++)
	{
		total += array[i];
	}
	return total;
}

int find(int key, int hashtable[], int n)
{
	int value = hash(key, n);
	int i = 0;
	int *record = (int *)calloc(n, sizeof(int));
	int address = value;
	int gap;
	while (hashtable[address] != key && sum(record, n) < n)
	{
		if (i % 2 == 0)
		{
			gap = i / 2;
			address = (value - gap * gap) % n;
		}
		else
		{
			gap = (i + 1) / 2;
			address = (value + gap * gap) % n;
		}
		record[address] = 1;
		i++;
	}
	free(record);
	if (hashtable[address] == key)
	{
		return address;
	}
	else
	{
		return -1;
	}
}

int insert(int key, int hashtable[], int n)
{
	int value = hash(key, n);
	int i = 0;
	int *record = (int *)calloc(n, sizeof(int));
	int address = value;
	int gap;
	while (hashtable[address] != -1 && sum(record, n) < n)
	{
		if (hashtable[address] == key)
		{
			break;
		}
		if (i % 2 == 0)
		{
			gap = i / 2;
			address = (value - gap * gap) % n;
		}
		else
		{
			gap = (i + 1) / 2;
			address = (value + gap * gap) % n;
		}
		record[address] = 1;
		i++;
	}
	free(record);
	if (hashtable[address] == -1)
	{
		hashtable[address] = key;
		return 1;
	}
	else if (hashtable[address] == key)
	{
		return 0;
	}
	else
	{
		return -1;
	}
}

int main()
{
	int map[11];
	int i;
	for (i = 0; i < 11; i++)
	{
		map[i] = -1;
	}
	for (i = 0; i < 11; i++)
	{
		printf("%d ", map[i]);
	}
	putchar('\n');
	int keys[] = {47, 7, 29, 11, 9, 84, 54, 20, 30};
	for (i = 0; i < 9; i++)
	{
		insert(keys[i], map, 11);
	}
	for (i = 0; i < 9; i++)
	{
		printf("%d-%d\n", find(keys[i], map, 11), keys[i]);
	}
	return 0;
}
